//
//  DPSolution.h
//  leetcode
//
//  Created by Ellie on 2021/1/26.
//  Copyright © 2021 Ellie. All rights reserved.
//

#ifndef DPSolution_h
#define DPSolution_h

#include "DataDefine.h"
#include <queue>
#include <unordered_map>
#include <string>
#include <stack>
#include <vector>
#include <iostream>
#include <sstream>

using namespace std;

class DPSolution
{
public:
    // 1143. 最长公共子序列
    // 通过递归可以看出来状态转换方程
    int longestCommonSubsequence(string text1, string text2);
    int lcsrecursion(string& s1, int n1, string& s2, int n2);
    
    // Bottom to Top
    int longestCommonSubsequenceiterative(string text1, string text2);
    
    // 300. 最长递增子序列 画图解决，想法
    int lengthOfLIS(vector<int>& nums);
    // 673. 最长递增子序列的个数 300的进阶版本，增加一个维护个数的维度，达到最长递增子序列的个数
    int findNumberOfLIS(vector<int>& nums);
    // 674. 最长连续递增序列,子数组问题 EASY
    int findLengthOfLCIS(vector<int>& nums);
    
    // 5. 最长回文子串 中间扩散方法解决，最长回文子串
    string longestPalindromeSimple(string s);
    string longestPalindrome(string s);
    // 647. 回文子串 统计回文子串的个数 给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。 中间扩散方法解决
    // 具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
    int countSubstringsSimple(string s);
    // 中间扩散方法，按照i，i为中心或者i，i+1为中心，偶数和奇数
    int expandpalindromicCheck(const string &s ,int i, int j, int size, int & left, int & len);
    // 516. 最长回文子序列 难度一般比字串难度大
    int longestPalindromeSubseq(string s);
    // 通过递归可以看出来状态转换方程，然后找出状态转换方程
    int longestPalindromeSubseqRecursion(string s);
    int longestPalindromeSubseqHelper(const string &, int i, int j, int size);
    
    // 53. 最大子序和 DP 或者 迭代思路，状态切换方程和152. 乘积最大子数组有点类似的解决思路
    int maxSubArraySimple(vector<int>& nums);
    // 斐波那契数列一样的理解思路，递归->dptalble->状态压缩
    int maxSubArray(vector<int>& nums);
    int maxSubArrayMinimumMem(vector<int>& nums);
    // 152. 乘积最大子数组，可以不用dp的解法，存在负数，负数会将最大值变成最小值，遇到负数交换下保存的最大值和最小值，根据
    // 当前的nums[i] 和乘积 更新保存的最大值和最小值
    int maxProduct(vector<int>& nums);
    
public:
    vector<int> intvectormem;
    vector<vector<int>> dp2dtable;
    int coinChange(vector<int>&coins, int amount)
    {
        intvectormem.resize(amount + 1);
        return doCoinChange(coins, amount);
    }
    // Coins Change problem
    // Top to Bottom;
    // with cache same subproblem
    int doCoinChange(vector<int>& coins, int amount)
    {
        // just break down
        if(amount < 0)
            return -1;
        // find right now
        if(amount == 0)
            return 0;
        int size = coins.size();
        int ret = INT_MAX;
        for(int i=0; i<size; i++)
        {
            int subproblem = doCoinChange(coins, amount - coins[i]);
            if(subproblem == -1 )
                continue;
            ret = min(ret, 1 + subproblem);
        }
        intvectormem[amount] = ret != INT_MAX ? ret : -1;
        return intvectormem[amount];
    }
    
    int canSum(vector<int>& numbers, int targetsum)
    {
        return 0;
    }
    
    int targetSum(vector<int>& numbers, int targetsum)
    {
        return 0;
    }
    
    int targetMinNumberSum(vector<int>& numbers, int targetsum)
    {
        return 0;
    }
    
    // 爬楼梯
    // 1,2
    // f(n) = f(n-1) + f(n-2);
    // 找到子问题和basebase
    unordered_map<int, int> memintint;
    int climbStairs(int n)
    {
        if(n == 1)
            return 1;
        if(n == 2)
            return 2;
        if(memintint.find(n) != memintint.end())
            return memintint[n];
        int value = climbStairs(n - 1) + climbStairs( n - 2);
        memintint[n] = value;
        return value;
    }
    
    // 1,2,3 每次可以走1步，2步或者3步
    // 1:1
    // 2:2
    // 3:1,2,3 = 4
    // 找到base-base
    int climbStairsN(int n)
    {
        if(n <=0 )
            return 0;
        if(n == 1)
            return 1;
        if(n == 2)
            return 2;
        if(n == 3)
            return 4;
        vector<int> dp(n+1);
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        for(int i=4;i<=n;i++)
        {
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
        }
        return dp[n];
    }
    
    unordered_map<int,int> intmap;
    int climStairNMethod(int n)
    {
        if(n < 0)
            return 0;
        else if( n == 0)
            return 1;
        else if(intmap.find(n) != intmap.end())
        {
            return intmap[n];
        }
        else
        {
            int value = climStairNMethod(n-1) + climStairNMethod(n-2) + climStairNMethod(n-3);
            intmap[n] = value;
            return value;
        }
    }
    
    // 还可以继续优化，因为发现只依赖
    int climStairsIteration(int n)
    {
        if(n <= 0)
            return 0;
        if(n == 1)
            return 1;
        if(n == 2)
            return 2;
        
        vector<int> dp(n+1);
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3;i<=n;i++)
        {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
    
    // 1-N 创建二叉搜树的个数,返回数量
    // 1-N 创建二叉树返回vector<TreeNode*> nodes;
    int countBSTWithN(int N)
    {
        return 0;
    }
    
    vector<TreeNode*> getAllBSTWithN(int N)
    {
        return vector<TreeNode*>();
    }
    
    // Grid 寻找路径
    // 变形，带有障碍物
    // 魔术索引 A[i] = i 没有重复值，进阶版本有重复值
    // N对括号的全部有效组合
    // 全排列
    // 颜色填充 floodfill
    // 八皇后问题
    unordered_map<string, int> memstringint;
    // m,n for keys
    // 反向解决问题，需要找到左边或者上边的两个节点一直，从m，n走到0，0
    int gridTraveler(int m, int n)
    {
        // MxN的格子，1-M，原点表示为【1，1】
        if(m == 0 || n == 0)
            return 0;
        if(m == 1 && n == 1)
            return 1;
        string key = to_string(m) + ',' + to_string(n);
        if(memstringint.find(key) != memstringint.end())
            return memstringint[key];
        int moveleft = gridTraveler(m - 1, n);
        int movetop = gridTraveler(m, n - 1);
        memstringint[key] = moveleft + movetop;
        return moveleft + movetop;
    }
    
    // dp[m,n] = dp[m-1][n] + dp[m][n-1];
    int gridTravelerwithDPFunction(int m, int n)
    {
        // dp[0][0] 不是一个合法的状态，我们需要忽略这一项，返回m-1，n-1
        // 而且走的时候需要到m-1和n-1即可
        vector<vector<int>> dp(m+1,vector<int>(n+1, 0));
        // dp[0,1],dp[1,0]
        dp[0][1] = 1;
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m][n];
    }
    
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        cout << "m:" << m << ",n:" << n << endl;
        // return uniquePathsWithObstacles(obstacleGrid, m ,n);
        return gridtravelObstacles(obstacleGrid, m, n);
    }
    
    // dp[m,n] = dp[m-1][n] + dp[m][n-1];
    // base-base dp[1][1] = 1
    int gridtravelObstacles(vector<vector<int>>& obstacleGrid, int m, int n)
    {
        // dp[0][0] 不是一个合法的状态，我们需要忽略这一项，返回m-1，n-1
        // 而且走的时候需要到m-1和n-1即可
        vector<vector<int>> dp(m+1,vector<int>(n+1, 0));
        // dp[0,1],dp[1,0]
        // dp[1][1] = dp[0][1] + dp[1][0] = 1
        // base base dp[1][1]=1，将dp[1][0] = 1 or dp[0][1] = 1是为了满足dp[1][1] = 1
        dp[0][1] = 1;
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(obstacleGrid[i-1][j-1] == 1)
                    dp[i][j] = 0;
                else
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m][n];
    }
    
    unordered_map<string, int> memstringstringint;
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid, int m, int n)
    {
        // MxN的格子，1-M，原点表示为【1，1】
        if(m == 0 || n == 0)
            return 0;
        if(obstacleGrid[m - 1][n - 1] == 1)
            return 0;
        if(m == 1 && n == 1)
            return 1;
        string key = to_string(m) + ',' + to_string(n);
        if(memstringstringint.find(key) != memstringstringint.end())
            return memstringstringint[key];
        
        int moveleft = uniquePathsWithObstacles(obstacleGrid, m - 1, n);
        int movetop = uniquePathsWithObstacles(obstacleGrid, m, n - 1);
        
        memstringstringint[key] = moveleft + movetop;
        return moveleft + movetop;
    }
};

#endif /* DPSolution_h */
